package com.cqs.leetcode.backtrack;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author lixqw
 * @date 2020/9/8
 */
public class StringPermutation {

    public String[] permutation(String s) {
        List<String> list = new ArrayList<>();
        permutation(s, 0, new boolean[s.length()], "", list);
        String[] cs = new String[list.size()];
        System.out.println(list);
        list.toArray(cs);
        return cs;
    }

    private void permutation(String s, int start, boolean[] used, String tmp, List<String> list) {
        if (start == s.length()) {
            list.add(tmp);
            return;
        }
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if (used[i] || set.contains(s.charAt(i))) continue;
            set.add(s.charAt(i));
            used[i] = true;
            permutation(s, start + 1, used, tmp + s.charAt(i), list);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        List<String> tests = new ArrayList<>();
        tests.add("abc");
        tests.add("aab");
        StringPermutation permutation = new StringPermutation();
        tests.forEach(permutation::permutation);
    }

}
